// https://leetcode.cn/problems/linked-list-cycle/
// Created by ade on 2022/7/27.
//
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    // 最普通的方法
    bool hasCycle1(ListNode *head) {
        unordered_map < ListNode * , int > myMap;
        while (head) {
            if (myMap.find(head) == myMap.end()) {
                myMap[head] = 1;
                head = head->next;
            } else {
                return true;
            }
        }
        return false;
    }

    // 快慢指针
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;
        ListNode *slow = head;
        ListNode *fast = head->next;
        while (fast->next) {
            slow = slow->next;
            fast = fast->next;
            if (slow == fast) return true;
            if (fast->next) {
                fast = fast->next;
            }
            if (slow == fast) return true;
        }

        return false;
    }
};

